// Swap method for arrays
Array.prototype.swap=function(a, b){
	var tmp=this[a];
	this[a]=this[b];
	this[b]=tmp;
}

function Sort(){
	
}

Sort.bubbleSort = function( arr ){

	var numItems = arr.length;
	var item, prevItem, temp;
	
	for ( var j=0; j < numItems;  j++ ){
		for ( var i=(numItems -1); i >= 0;  i-- ){
			item = arr[i];
			prevItem = arr[i-1];
			Counter.increment('bubblesort_comparisons');
			if ( prevItem > item ){
				arr.swap(i, (i-1));
			}
		}
	}
}

Sort.quickSort = function( arr ){
	var numItems = arr.length;
    if (numItems < 2)
        return arr;

	// Select the pivot
	var pivotIdx = Math.floor((Math.random()*numItems));
	var pivotValue = arr[pivotIdx];
 
	var left = 0,
		right = (numItems - 1);

	while( left < right ){
		while( arr[left] < pivotValue ){
			left++;
		}
		while( arr[right] > pivotValue ){
			right--;
		}
		arr.swap( left, right );
	}
	var smaller = arr.slice(0, left);
	var larger = arr.slice((right + 1), numItems);

	return Sort.quickSort(smaller).concat([pivotValue], Sort.quickSort(larger));
}
